Runtime Analysis of the $(1+(\lambda,\lambda))$ Genetic Algorithm on Random Satisfiable 3-CNF Formulas

摘要

The $(1+(\lambda,\lambda))$ genetic algorithm, first proposed at GECCO 2013,showed a surprisingly good performance on so me optimization problems. Thetheoretical analysis so far was restricted to the OneMax test function, wherethis GA profited from the perfect fitness-distance correlation. In this work,we conduct a rigorous runtime analysis of this GA on random 3-SAT instances inthe planted solution model having at least logarithmic average degree, whichare known to have a weaker fitness distance correlation. We prove that this GA with fixed not too large population size again obtainsruntimes better than $\Theta(n \log n)$, which is a lower bound for mostevolutionary algorithms on pseudo-Boolean problems with unique optimum.However, the self-adjusting version of the GA risks reaching population sizesat which the intermediate selection of the GA, due to the weakerfitness-distance correlation, is not able to distinguish a profitable offspringfrom others. We show that this problem can be overcome by equipping theself-adjusting GA with an upper limit for the population size. Apart fromsparse instances, this limit can be chosen in a way that the asymptoticperformance does not worsen compared to the idealistic OneMax case. Overall,this work shows that the $(1+(\lambda,\lambda))$ GA can provably have a goodperformance on combinatorial search and optimization problems also in thepresence of a weaker fitness-distance correlation.